package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

 * 示例 1：
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 *
 * 链接：https://leetcode-cn.com/problems/merge-intervals
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class MergeIntervals {
    /**
     * 1.将数组按照start部分进行排序
     * 2.从小到大依次将数组放入到结果数组
     * 3.在放入的过程中，将要放入的数组的start和结果数组中最后一个数字的end部分进行比较(这里我用O表示结果数组中最后一个数组对，N表示将要放入的数组)。
     *   3.1 如果Nstart <= Oend 那么 Oend = Max(Nend, Oend)
     *   3.2 如果 Nstart > Oend 那么直接放入到结果数组
     * */
    class Solution {
        public int[][] merge(int[][] intervals) {
            if(intervals.length == 0){
                return new int[0][0];
            }
            // 排序
            Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
            List<int[]> result = new ArrayList<>();
            result.add(intervals[0]);
            for (int i = 1; i < intervals.length; i++) {
                if(intervals[i][0] <= result.get(result.size()-1)[1]){
                    result.get(result.size()-1)[1] = Math.max(intervals[i][1],result.get(result.size()-1)[1]);
                }else{
                    result.add(intervals[i]);
                }
            }
            return result.toArray(new int[result.size()][]);
        }
    }
}
